package lc;

import java.util.Stack;

import ch4tree.BTreePrinter;
import ch4tree.Chapter;
import ch4tree.TreeNode;

public class SumRootToLeafNumbers {

    public int sumNumbers(TreeNode root) {
    	if (root == null) {
    		return 0;
    	}
    	Stack<TreeNode> stack = new Stack<TreeNode>();
    	
    	int sum=traverse(root, stack);
    	
    	return sum;
    }
    
    static int traverse(TreeNode root, Stack<TreeNode> stack) {
    	stack.push(root);
    	if (root.left == null && root.right == null) {
			StringBuilder sb = new StringBuilder();
			for (TreeNode n : stack) {
				sb.append(n.val);
			}
			stack.pop();
			return Integer.parseInt(sb.toString());    		
    	}
    	
    	int left = 0;
    	if (root.left != null) {
    		left = traverse(root.left, stack);
    	}
    	
    	int right = 0;
    	if (root.right != null) {
    		right = traverse(root.right, stack);
    	}
    	
    	stack.pop();
    	return left+right;
    }

    public static void main(String ...strings) {
    	SumRootToLeafNumbers sol = new SumRootToLeafNumbers();
		TreeNode bst = Chapter.createMinimalBST(new int [] {1, 2, 3, 4, 5});
		BTreePrinter.printNode(bst);
		int sumNumbers = sol.sumNumbers(bst);
		System.out.println(sumNumbers);
    }
}
